/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


// 二叉树的层序遍历（BFS(one queue/two queues)/DFS）
class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Level order a list of lists of integer
     */
     
    // BFS, 2 queues, 个
    // vector<vector<int>> levelOrder(TreeNode * root) {
    //     queue<TreeNode*> q1;
    //     queue<TreeNode*> q2;
    //     q1.push(root);
    //     vector<vector<int>> result;
    //     if (!root)
    //     {
    //         return result;
    //     }
    //     while (!q1.empty() || !q2.empty())
    //     {
    //         vector<int> tmp;
    //         while (!q1.empty())
    //         {
    //             root = q1.front();
    //             q1.pop();
    //             tmp.push_back(root->val);
    //             if (root->left) q2.push(root->left);
    //             if (root->right) q2.push(root->right);
    //         }
    //         if (!tmp.empty())
    //         {
    //             result.push_back(tmp);
    //             tmp.clear();
    //         }
    //         while (!q2.empty())
    //         {
    //             root = q2.front();
    //             q2.pop();
    //             tmp.push_back(root->val);
    //             if (root->left) q1.push(root->left);
    //             if (root->right) q1.push(root->right);
    //         }
    //         if (!tmp.empty())
    //         {
    //             result.push_back(tmp);
    //         }
    //     }
    //     return result;
    // }
    
    // BFS, 2 queues, better
    // 省去重复代码的方法：交换q1，q2
    vector<vector<int>> levelOrder(TreeNode * root) {
        queue<TreeNode*> q1;
        q1.push(root);
        vector<vector<int>> result;
        if (!root)
        {
            return result;
        }
        while (!q1.empty())
        {
            queue<TreeNode*> q2;
            vector<int> tmp;
            while (!q1.empty())
            {
                root = q1.front();
                q1.pop();
                tmp.push_back(root->val);
                if (root->left) q2.push(root->left);
                if (root->right) q2.push(root->right);
            }
            if (!tmp.empty())
            {
                result.push_back(tmp);
            }
            // queue<TreeNode*> t = q1;
            // q1 = q2;
            // q2 = t;
            q1 = q2;
        }
        return result;
    }
    
    
    // BFS, 1 queue，通过size控制
    // vector<vector<int>> levelOrder(TreeNode * root) {
    //     queue<TreeNode*> q1;
    //     q1.push(root);
    //     vector<vector<int>> result;
    //     if (!root)
    //     {
    //         return result;
    //     }
    //     while (!q1.empty())
    //     {
    //         vector<int> tmp;
    //         int s = q1.size();
    //         for (int i = 0; i < s; ++i)
    //         {
    //             root = q1.front();
    //             q1.pop();
    //             tmp.push_back(root->val);
    //             if (root->left) q1.push(root->left);
    //             if (root->right) q1.push(root->right);
    //         }
    //         // if (!tmp.empty())
    //         {
    //             result.push_back(tmp);
    //         }
    //     }
    //     return result;
    // }
    
    
    // DFS
    // resut不加入递归的写法
    // void dfs(TreeNode * root, int curtLevel, int maxLevel, vector<int>& level)
    // {
    //     if (!root)
    //     {
    //         return;
    //     }
    //     if (curtLevel == maxLevel) //虽然用的DFS, 但达到这个高度的才加进去
    //     {
    //         level.push_back(root->val);
    //         return;
    //     }
    //     dfs(root->left, curtLevel + 1, maxLevel, level);
    //     dfs(root->right, curtLevel + 1, maxLevel, level);
    // }
    
    // vector<vector<int>> levelOrder(TreeNode * root) {
    //     vector<vector<int>> result;
    //     int maxLevel = 0;
    //     vector<int> level;
    //     while (true)
    //     {
    //         level.clear();
    //         dfs(root, 0, maxLevel, level);
    //         if (level.empty())
    //         {
    //             break;
    //         }
    //         result.push_back(level);
    //         maxLevel++;
    //     }
    //     return result;
    // }


    // result加入递归的写法
    // void dfs(vector<vector<int>>& result, int depth, TreeNode *node)
    // {
    //     if (!node)
    //     {
    //         return;
    //     }
    //     if (depth == result.size())
    //     {
    //         result.push_back(vector<int>()); //新对象这样加
    //     }
    //     result[depth].push_back(node->val);
    //     dfs(result, depth + 1, node->left);
    //     dfs(result, depth + 1, node->right);
    // }
    // vector<vector<int>> levelOrder(TreeNode * root) {
    //     vector<vector<int>> result;
    //     if (!root)
    //     {
    //         return result;
    //     }
    //     dfs(result, 0, root);
    //     return result;
    // }
};